In a computing device, multiple requesters (e.g., software threads, processors, or other hardware) may contend for access to a shared object such as, for example, a critical section in a memory, a shared data structure, a semaphore, or other suitable shared resources. An arbitration scheme is typically used so that only one requester can access the shared object at a time. The arbitration scheme uses a lock (i.e., synchronization object) that is associated with the shared object so that the other requesters will be blocked from accessing the shared object until the current requester has completed its operation in the shared object and has released the lock. The lock is typically a bit value that is set in a memory location of the shared object. Typically, the lock will have a bit value (logical “1” or logical “0”) that is set by the requester when the requester has ownership of the lock.
Busy waiting is a commonly-used method for improving the throughput (rate) of acquisition of locks for shared objects. A software thread is a stream of instructions that are being executed by a processor. When a software thread performs busy waiting (i.e., spinning), the software thread will wait (spin) for a lock to become available and may obtain the lock after the lock is released by another thread that is currently holding the lock. Threads wanting access to a currently unavailable shared object will busy wait for some amount of time (provided that busy waiting is permitted by the system) and will eventually go into a sleep state if the thread is unable to obtain the lock within that time amount for busy waiting. As known to those skilled in the art, busy waiting is when the thread waits for an event (e.g., availability of the lock) by spinning through a tight loop or a timed-delay loop that polls for the event on each pass by the thread through the loop. As also known to those skilled in the art, when a thread is placed in the sleep state, the thread is deactivated by a scheduler and the thread is then re-activated when a given external event occurs such as, for example, the expiration of the sleep time period. In the sleep state, the thread is typically placed in a queue of threads waiting for the lock. When a thread is placed in the sleep state, the thread does not consume a significant amount of processor time.
However, too much busy waiting or having too many threads that are busy waiting can waste processor power. Also, having too many threads that are busy waiting can also increase the bus traffic in the computer system after the lock is released because all of the threads that are busy waiting will contend for the released lock. In contrast, too little busy waiting can result in a low throughput of acquisition of locks. In addition, for critical sections where the hold time for a lock is typically large, having many busy waiters can waste processing power. On the other hand, when the hold time for a lock is small, having many busy waiters (i.e., threads in the busy waiting state) can greatly increase the lock acquisition throughput but can also waste processor power due to the spin cycles by the waiting threads. Therefore, having a fixed number of busy waiters or allowing all threads to busy wait may not result in efficient behavior of the computer system in all instances.
Most previous mechanisms that attempt to control the amount of wasted processor time in busy waiting involve using a fixed number of busy waiters. For example, Solaris® from SUN MICROSYSTEMS, INCORPORATED, provides a method to control the maximum number of busy waiters that are allowed for their pthread mutexes (POSIX-standard tread mutual exclusion). However, the method used in Solaris does not appear to dynamically adjust the number of busy waiters, and instead caps (limits) the number of busy waiters at a maximum value. While this method may provide good performance, this method may also disadvantageously waste processing resources for highly contended locks with both short hold times and long hold times for the locks.
Other known previous approaches focus on making the busy waiting as efficient as possible with regard to reducing the bus activity after the lock is released, but do not disclose in dynamically adjusting the number of busy waiters.
Therefore, the current technology is limited in its capabilities and suffers from at least the above constraints and deficiencies.